import java.util.ArrayList;
import java.util.Set;

/**
 * Created by xiebang
 * Description
 * User:小谢
 * Date:2021-11-03
 * Time:18:07
 */
public class test {

}
//public class Solution {
//    public boolean wordBreak(String s, Set<String> dict) {
//        boolean[] canBreak = new boolean[s.length() + 1];
//
//        canBreak[0] = true;
//        for (int i = 1;i <= s.length();++i){
//            // j < i && [j + 1,i]
//            for (int j = 0; j < i; j++) {
//                if (canBreak[j] && dict.contains(s.substring(j,i))){
//                    canBreak[i] = true;
//                }
//            }
//        }
//        return canBreak[s.length()];
//    }
//}


class Solution {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle.isEmpty()){
            return 0;
        }
        int row = triangle.size();
        //创建二位数组
        ArrayList<ArrayList<Integer>> minpathSum = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            minpathSum.add(new ArrayList<>());
        }


        //初始化值F[0][0]
        minpathSum.get(0).add(triangle.get(0).get(0));

        for (int i = 1; i < row; i++) {
            int curpath = 0;

            for (int j = 0; j <= i; j++) {
                if (j == 0){
                    curpath = minpathSum.get(i - 1).get(0);
                }else if (j == i){
                    curpath = minpathSum.get(i - 1).get( j -1);
                }else {
                    curpath = Math.min(minpathSum.get(i-1).get(j - 1),minpathSum.get(i - 1).get(j));
                }
                minpathSum.get(i).add(curpath + triangle.get(i).get(j));
            }
        }


        int min = minpathSum.get(row - 1).get(0);

        for (int i = 1; i < row; i++) {
            if (min > minpathSum.get(row - 1).get(i)){
                min = minpathSum.get(row - 1).get(i);
            }

        }
        return min;
    }
}

class Solution1 {
    public int minimumTotal(ArrayList<ArrayList<Integer>> triangle) {
        if (triangle.isEmpty()){
            return 0;
        }
        int row = triangle.size();
        //创建二位数组
        ArrayList<ArrayList<Integer>> minpathSum = new ArrayList<>();
        for (int i = 0; i < row; i++) {
            minpathSum.add(new ArrayList<>());
        }


        //初始化值F[0][0]
        for (int i = 0; i < row; i++) {
            minpathSum.get(row - 1).add(triangle.get(row - 1).get(i));
        }

        //转移函数
        for (int i = row - 2; i >= 0 ; i--) {
            int curpath = 0;

            for (int j = 0; j <= i; j++) {
                curpath = Math.min(minpathSum.get(i + 1).get(j),minpathSum.get(i + 1).get(j + 1));
                triangle.get(i).add(curpath);
                minpathSum.get(i).add(curpath + triangle.get(i).get(j));
            }
        }

        return minpathSum.get(0).get(0);
    }
}